#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct {
    LinkNode *front,*rear; //链表头，链表尾 ，队头队尾
}LinkQueue;  //先进先出

//队列初始化，使用的是带头结点的链表来实现
void InitQueue(LinkQueue &Q)
{
    Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next=NULL;  //头结点的next指针为NULL
}

bool IsEmpty(LinkQueue Q)
{
    if(Q.front==Q.rear)
    {
        return true;
    } else{
        return false;
    }
}
//入队
void EnQueue(LinkQueue &Q,ElemType x)
{
    LinkNode *pnew=(LinkNode*)malloc(sizeof(LinkNode));
    pnew->data=x;
    pnew->next=NULL;    //要让next为NULL，这样才知道尾节点在哪结束
    Q.rear->next=pnew;  //尾指针的next要指向pnew，因为从尾部入队
    Q.rear=pnew;  //rear要指向新的尾部
}
//出队
bool DeQueue(LinkQueue &Q,ElemType &x)
{
    if(Q.front==Q.rear)
    {
        return false;
    }
    LinkNode *q=Q.front->next;
    x=q->data;    //获取要出队的元素值
    Q.front->next=q->next;  //让结点断链
    if(Q.rear==q)           //链表只剩下一个结点时，被删除后要改变rear
    {
        Q.rear=Q.front;
    }
    free(q);
    return true;
}

int main() {
    LinkQueue Q;
    InitQueue(Q);  //初始化队列
    bool ret;
    EnQueue(Q,3);
    EnQueue(Q,4);
    EnQueue(Q,5);
    EnQueue(Q,6);
    EnQueue(Q,7);

    ElemType element;
    ret=DeQueue(Q,element);
    if(ret)
    {
        printf("DeQueue successfully, element is %d\n",element);
    } else{
        printf("DeQueue failed\n");
    }
    return 0;
}
